package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: combine
 * @author: chanzhugang
 * @create: 2022/08/04 21:34
 */
public class Combine {

    /**
     * 77 组合
     *
     * @param n
     * @param k
     * @return
     */
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        // [1, n]中k（组合长度为k）个数的组合
        backtrack(n, k, 1, new ArrayList<Integer>());
        return result;
    }

    /**
     * @param n
     * @param k
     * @param step 阶段  1 - n
     * @param path 路径
     *             step选与不选 - 可选列表
     */
    private void backtrack(int n, int k, int step, List<Integer> path) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (step == n + 1) {
            return;
        }
        // 不选
        backtrack(n, k, step + 1, path);

        //选
        path.add(step);
        backtrack(n, k, step + 1, path);
        path.remove(path.size() - 1);
    }
}